package com.igeek.array;

import java.util.Arrays;

/**
 * 数组的排序
 */
public class Demo03 {

    /**
     * 冒泡排序的一种形式：最小值向前冒
     * 两两交换
     * @param nums
     */
    public static void bubbleSort1(int[] nums){

        //外层循环控制轴值
        for(int i = 0;i<nums.length;i++){

            for(int j = i+1;j<nums.length;j++){

                if(nums[i] > nums[j]){
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
            System.out.println("第"+(i+1)+"趟循环的结果"+ Arrays.toString(nums));
        }
    }
    /**
     * 冒泡排序的一种形式：最大值向后冒
     * 两两交换
     * @param nums
     */
    public static void bubbleSort2(int[] nums){

        //外层循环控制趟数
        for(int i = 0;i<nums.length;i++){

            //内存循环做前后两个数的比较
            for(int j = 0;j<nums.length-1;j++){

                if (nums[j] > nums[j+1]) {

                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
            System.out.println("第"+(i+1)+"趟循环的结果"+ Arrays.toString(nums));
        }
    }


    /**
     * 选择排序，假定一个最小值，然后，将后面的数分别与最小值比较，如果小于该假定的最小值，则两个数进行交换
     * @param nums
     */
    public static void selectSort(int[] nums){

        //外层循环控制趟数
        for(int i = 0;i<nums.length;i++){

            int min = nums[i];
            int minIndex = i;

            //内层循环控制最小值的比较
            for(int j = i+1;j<nums.length;j++){

                if(nums[j] < min){
                    min = nums[j];
                    minIndex = j;
                }
            }

            //比较一趟之后，判断假定的最小值是否发生了改变
            if(min != nums[i]){
                nums[minIndex] = nums[i];
                nums[i] = min;
            }
            System.out.println("第"+(i+1)+"趟循环的结果"+ Arrays.toString(nums));
        }

    }

    /**
     * 插入排序，保障前部分的数据是有序的，依次向有序的数据插入值，保证有序性
     * @param nums
     */
    public static void insertSort(int[] nums){

        //外层循环控制趟数
        for(int i = 0;i<nums.length;i++){

            //内层循环保证数据有序
            for(int j = i;j>0;j--){

                if(nums[j] < nums[j-1]){

                    int temp = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = temp;
                }else{
                    break;
                }
            }
            System.out.println("第"+(i+1)+"趟循环的结果"+ Arrays.toString(nums));
        }
    }

    /**
     * 快速排序
     * @param nums  无序数据
     * @param low   从左侧开始查找
     * @param high  从右侧开始查询
     */
    public static void quickSort(int[] nums,int low,int high){

        if(low > high){
            return;
        }
        int i = low;
        int j = high;

        //声明一个轴值
        int temp = nums[low];

        while (i < j){

            //先从右侧开始，找一个比轴值小的数
            while (temp <= nums[j] && i<j){
                j--;
            }

            //再从左侧开始，找一个比轴值大的数
            while (temp >= nums[i] && i<j){
                i++;
            }

            //找到了比轴值小的数，和，比轴值大的数，需要交换位置
            if(i < j){
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }

        //最后需要将 i 和 j重合的位置，与轴值做交换
        nums[low] = nums[i];
        nums[i] = temp;

        System.out.println("实现二分查找："+Arrays.toString(nums));

        //使用递归调用，分别将轴值左侧、右侧的数组，以相同的方式，进行遍历查找
        quickSort(nums,low,j-1);
        quickSort(nums,j+1,high);
    }

    public static void main(String[] args) {
        int[] nums = {42,71,39,69,49,7,15,68,241};
//        bubbleSort1(nums);

//        bubbleSort2(nums);

//        selectSort(nums);

//        insertSort(nums);

        quickSort(nums,0,nums.length-1);


    }

}
